package com.lw.leetcode.sort.c;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 850. 矩形面积 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/16 13:49
 */
public class RectangleArea {

    public static void main(String[] args) {
        RectangleArea test = new RectangleArea();


        String str = "[[49,40,62,100],[11,83,31,99],[19,39,30,99]]";

        System.out.println(str.replace("[", "{").replace("]", "}"));

        // 6
//        int[][] rectangles = {{0,0,2,2},{1,0,2,3},{1,0,3,1}};

        // 18
//        int[][] rectangles = {{0,0,3,3},{2,0,5,3},{1,1,4,4}};

        // 1584
//        int[][] rectangles = {{49,40,62,100},{11,83,31,99},{19,39,30,99}};

        // 49
//        int[][] rectangles = {{0,0,1000000000,1000000000}};

        // 7
        int[][] rectangles = {{0, 0, 2, 2}, {1, 1, 3, 3}};

        int i = test.rectangleArea(rectangles);
        System.out.println(i);
    }

    public int rectangleArea(int[][] rectangles) {
        int length = rectangles.length << 1;
        TreeMap<Integer, Integer>[] maps = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            maps[i] = new TreeMap<>();
        }
        int[] arr = new int[length];
        int i = 0;
        for (int[] rectangle : rectangles) {
            arr[i++] = rectangle[0];
            arr[i++] = rectangle[2];
        }
        Arrays.sort(arr);
        int st = arr[0];
        for (int j = 1; j < length; j++) {
            int end = arr[j];
            if (st == end) {
                continue;
            }
            TreeMap<Integer, Integer> map = maps[j];
            for (int[] rectangle : rectangles) {
                int l = rectangle[1];
                int h = rectangle[3];
                if (rectangle[0] <= st && rectangle[2] >= end) {
                    Map.Entry<Integer, Integer> fe = map.floorEntry(l);
                    if (fe != null && fe.getValue() >= l) {
                        if(fe.getValue() >= h) {
                            continue;
                        }
                        l = fe.getKey();
                    }
                    while (true) {
                        Map.Entry<Integer, Integer> le = map.ceilingEntry(l);
                        if (le == null || le.getKey() > h) {
                            map.put(l, h);
                            break;
                        }
                        map.remove(le.getKey());
                        if (le.getValue() >= h) {
                            map.put(l, le.getValue());
                            break;
                        }
                    }
                }

            }
            st = end;
        }
        long sum = 0;
        st = arr[0];
        for (int j = 1; j < length; j++) {
            int end = arr[j];
            if (st == end) {
                continue;
            }
            TreeMap<Integer, Integer> m = maps[j];
            long s = 0;
            for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
                s += entry.getValue() - entry.getKey();
            }
            sum += s * (end - st);
            st = end;
        }
        return (int) (sum % 1000000007);
    }


}




